// https://www.lintcode.com/problem/shortest-unordered-array/

public class Solution {
    /**
     * @param arr: an array of integers
     * @return: the length of the shortest possible subsequence of integers that are unordered
     */
    public int shortestUnorderedArray(int[] arr) {
        // write your code here
        boolean asc = arr[1] > arr[0];
        for (int i = 0; i < (arr.length - 1); ++i) {
            if (asc) {
                if (arr[i + 1] < arr[i]) {
                    return 3;
                }
            } else {
                if (arr[i + 1] > arr[i]) {
                    return 3;
                }
            }
        }
        return 0;
    }
}